{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Dessert Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最接近目标价格的甜点成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你打算做甜点，现在需要购买配料。目前共有 <code>n</code> 种冰激凌基料和 <code>m</code> 种配料可供选购。而制作甜点需要遵循以下几条规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>必须选择 <strong>一种</strong> 冰激凌基料。</li>\n",
    "\t<li>可以添加 <strong>一种或多种</strong> 配料，也可以不添加任何配料。</li>\n",
    "\t<li>每种类型的配料 <strong>最多两份</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你以下三个输入：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>baseCosts</code> ，一个长度为 <code>n</code> 的整数数组，其中每个 <code>baseCosts[i]</code> 表示第 <code>i</code> 种冰激凌基料的价格。</li>\n",
    "\t<li><code>toppingCosts</code>，一个长度为 <code>m</code> 的整数数组，其中每个 <code>toppingCosts[i]</code> 表示 <strong>一份</strong> 第 <code>i</code> 种冰激凌配料的价格。</li>\n",
    "\t<li><code>target</code> ，一个整数，表示你制作甜点的目标价格。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你希望自己做的甜点总成本尽可能接近目标价格 <code>target</code> 。</p>\n",
    "\n",
    "<p>返回最接近<em> </em><code>target</code> 的甜点成本。如果有多种方案，返回 <strong>成本相对较低</strong> 的一种。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>baseCosts = [1,7], toppingCosts = [3,4], target = 10\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>考虑下面的方案组合（所有下标均从 0 开始）：\n",
    "- 选择 1 号基料：成本 7\n",
    "- 选择 1 份 0 号配料：成本 1 x 3 = 3\n",
    "- 选择 0 份 1 号配料：成本 0 x 4 = 0\n",
    "总成本：7 + 3 + 0 = 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>baseCosts = [2,3], toppingCosts = [4,5,100], target = 18\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>考虑下面的方案组合（所有下标均从 0 开始）：\n",
    "- 选择 1 号基料：成本 3\n",
    "- 选择 1 份 0 号配料：成本 1 x 4 = 4\n",
    "- 选择 2 份 1 号配料：成本 2 x 5 = 10\n",
    "- 选择 0 份 2 号配料：成本 0 x 100 = 0\n",
    "总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>baseCosts = [3,10], toppingCosts = [2,5], target = 9\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>baseCosts = [10], toppingCosts = [1], target = 1\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>注意，你可以选择不添加任何配料，但你必须选择一种基料。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == baseCosts.length</code></li>\n",
    "\t<li><code>m == toppingCosts.length</code></li>\n",
    "\t<li><code>1 <= n, m <= 10</code></li>\n",
    "\t<li><code>1 <= baseCosts[i], toppingCosts[i] <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= target <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-dessert-cost](https://leetcode.cn/problems/closest-dessert-cost/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-dessert-cost](https://leetcode.cn/problems/closest-dessert-cost/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7]\\n[3,4]\\n10', '[2,3]\\n[4,5,100]\\n18', '[3,10]\\n[2,5]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        m, n = len(toppingCosts), len(baseCosts)\n",
    "        d = inf\n",
    "        ans = 0\n",
    "\n",
    "        def bk(idx, t):\n",
    "            nonlocal d, ans\n",
    "            if idx == m or t >= target:\n",
    "                if abs(target - t) < d:\n",
    "                    d = abs(target - t)\n",
    "                    ans = t\n",
    "                elif abs(target - t) == d and t < ans:\n",
    "                    ans = t\n",
    "                return \n",
    "            \n",
    "            for x in range(3):\n",
    "                bk(idx + 1, t + x * toppingCosts[idx])\n",
    "\n",
    "        for i in range(n):\n",
    "            bk(0, baseCosts[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        x = min(baseCosts)\n",
    "        if x > target:\n",
    "            return x\n",
    "        can = [False] * (target + 1)\n",
    "        ans = 2 * target - x\n",
    "        for c in baseCosts:\n",
    "            if c <= target:\n",
    "                can[c] = True\n",
    "            else:\n",
    "                ans = min(ans, c)\n",
    "        for c in toppingCosts:\n",
    "            for count in range(2):\n",
    "                for i in range(target, 0, -1):\n",
    "                    if can[i] and i + c > target:\n",
    "                        ans = min(ans, i + c)\n",
    "                    if i - c > 0 and not can[i]:\n",
    "                        can[i] = can[i - c]\n",
    "        for i in range(ans - target + 1):\n",
    "            if can[target - i]:\n",
    "                return target - i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        mmin = min(baseCosts)\n",
    "        if mmin >= target:\n",
    "            return mmin\n",
    "        up = 2 * target - mmin\n",
    "\n",
    "        dp = [False] * (target + 1)\n",
    "        for base in baseCosts:\n",
    "            if base <= target:\n",
    "                dp[base] = True\n",
    "            elif base < up:\n",
    "                up = base\n",
    "        top = min(target, max(baseCosts))\n",
    "        for x in sorted(toppingCosts * 2):\n",
    "            for i in range(top, mmin - 1, -1):\n",
    "                if not dp[i]:\n",
    "                    continue\n",
    "                y = i + x\n",
    "                if y > target:\n",
    "                    if y < up:\n",
    "                        up = y\n",
    "                else:\n",
    "                    dp[y] = True\n",
    "            top = min(top + x, target)\n",
    "        for x in range(target, 2 * target - up - 1, -1):\n",
    "            if dp[x]:\n",
    "                return x\n",
    "        return up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        sign, res = 1, float('inf')\n",
    "        def dfs(i, rest, s):\n",
    "            nonlocal sign \n",
    "            nonlocal res \n",
    "            if i == m or s == 1:\n",
    "                if rest < res:\n",
    "                    res = rest \n",
    "                    sign = s \n",
    "                elif rest == res and s == -1:\n",
    "                    sign = -1 \n",
    "                return \n",
    "            for k in range(min(2, rest//toppingCosts[i] + 1) + 1):\n",
    "                r = rest - k * toppingCosts[i] \n",
    "                dfs(i+1, abs(r), 1 if r < 0 else -1)\n",
    "        for i in range(n):\n",
    "            if target >= baseCosts[i]:\n",
    "                dfs(0, target-baseCosts[i], -1)\n",
    "            else:\n",
    "                dfs(0, -target+baseCosts[i], 1)\n",
    "        return target + res * sign \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        # 官方给的dp理解的不太顺畅，给出网友的（更好理解的思路）\n",
    "        x = min(baseCosts)\n",
    "        if x >= target:\n",
    "            return x\n",
    "        upper = 2 * target - x\n",
    "        dp = [False] * upper\n",
    "        for baseCost in baseCosts:\n",
    "            if baseCost < upper:\n",
    "                dp[baseCost] = True\n",
    "        for toppingCost in toppingCosts:\n",
    "            for i in range(upper - 1,x - 1, -1):\n",
    "                if dp[i] and (i + toppingCost < upper):\n",
    "                    dp[i + toppingCost] = True\n",
    "                if dp[i] and (i + 2 * toppingCost < upper):\n",
    "                    dp[i + 2 * toppingCost] = True\n",
    "        ans = x\n",
    "        for j in range(x + 1,upper):\n",
    "            if dp[j]:\n",
    "                if abs(j - target) < abs(ans - target):\n",
    "                    ans = j\n",
    "                elif abs(j - target) == abs(ans - target):\n",
    "                    ans = min(ans,j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "        arr = [list(set(baseCosts))]\n",
    "\n",
    "        for tc in toppingCosts:\n",
    "            arr.append([0, tc, 2 * tc])\n",
    "        \n",
    "        ret = inf\n",
    "        def dfs(idx, v):\n",
    "\n",
    "            #print(f'{idx} {v}')\n",
    "            nonlocal ret\n",
    "\n",
    "            if target == ret:\n",
    "                return\n",
    "\n",
    "            if abs(v-target) < abs(ret-target) or (abs(v-target) == abs(ret-target) and v < ret):\n",
    "                if v != 0:\n",
    "                    ret = v\n",
    "\n",
    "            if idx == len(arr):\n",
    "                return\n",
    "                \n",
    "            if v > target:\n",
    "                return\n",
    "\n",
    "            for c in arr[idx]:\n",
    "                dfs(idx+1, v + c)\n",
    "\n",
    "        dfs(0, 0)\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n = len(baseCosts)\n",
    "        m = len(toppingCosts)\n",
    "        min_res = inf\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            nonlocal sm, min_res, ans\n",
    "            if i == m:\n",
    "                if abs(sm-target) < min_res:\n",
    "                    min_res = abs(sm-target)\n",
    "                    ans = sm\n",
    "                elif abs(sm-target) == min_res and sm < target:\n",
    "                    ans = sm\n",
    "                return \n",
    "            for j in range(3):\n",
    "                sm+=toppingCosts[i]*j\n",
    "                dfs(i+1)\n",
    "                sm-=toppingCosts[i]*j\n",
    "        for i in range(n):\n",
    "            sm = baseCosts[i]\n",
    "            dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, \n",
    "                    baseCosts: List[int], \n",
    "                    toppingCosts: List[int], \n",
    "                    target: int) -> int:\n",
    "\n",
    "        baseCosts.sort()\n",
    "        toppingCosts.sort()\n",
    "\n",
    "        n = len(toppingCosts)\n",
    "        ans = sys.maxsize\n",
    "        path = []\n",
    "\n",
    "        def dfs(b, v, k):\n",
    "            nonlocal ans\n",
    "            cur = b + v\n",
    "            if abs(cur - target) < abs(ans - target):\n",
    "                ans = cur\n",
    "            elif abs (cur - target) == abs(ans - target):\n",
    "                if cur < ans:\n",
    "                    ans = cur\n",
    "            else:\n",
    "                if cur > target:\n",
    "                    return\n",
    "            if k == n:\n",
    "                return\n",
    "            \n",
    "            dfs(b, v, k + 1)\n",
    "            dfs(b, v + toppingCosts[k], k + 1)\n",
    "            dfs(b, v + 2 * toppingCosts[k], k + 1)\n",
    "        \n",
    "        for b in baseCosts:\n",
    "            if b == target:\n",
    "                return b\n",
    "            dfs(b, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        x = min(baseCosts)\n",
    "        if x > target:\n",
    "            return x\n",
    "        can = [False] * (target + 1)\n",
    "        ans = 2 * target - x # 取一个不可能的值\n",
    "        for c in baseCosts:\n",
    "            if c <= target:\n",
    "                can[c] = True\n",
    "            else:\n",
    "                ans = min(ans, c)\n",
    "        # 0-1背包，先物品后背包，背包逆序\n",
    "        for c in toppingCosts:\n",
    "            for count in range(2):\n",
    "                for i in range(target, 0, -1):\n",
    "                    # 大于则直接更新ans\n",
    "                    if can[i] and i + c > target:\n",
    "                        ans = min(ans, i + c)\n",
    "                    # 小于则先加上\n",
    "                    if i - c > 0 and not can[i]:\n",
    "                        can[i] = can[i - c]\n",
    "        for i in range(ans - target + 1):\n",
    "            if can[target - i]:\n",
    "                return target - i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n,m=len(baseCosts),len(toppingCosts)\n",
    "        baseCosts.sort()\n",
    "        self.ans = baseCosts[0]\n",
    "\n",
    "        def travel(pos, temp_sum):\n",
    "            if pos==m:\n",
    "                idx = bisect_left(baseCosts, target-temp_sum)\n",
    "                if idx>0:\n",
    "                    k = baseCosts[idx-1]+temp_sum\n",
    "                    if abs(k-target)<abs(self.ans-target) or \\\n",
    "                        (abs(k-target)==abs(self.ans-target) and k<self.ans):\n",
    "                        self.ans = k\n",
    "                if idx<n:\n",
    "                    k = baseCosts[idx]+temp_sum\n",
    "                    if abs(k-target)<abs(self.ans-target) or \\\n",
    "                        (abs(k-target)==abs(self.ans-target) and k<self.ans):\n",
    "                        self.ans = k\n",
    "                return\n",
    "            travel(pos+1, temp_sum)\n",
    "            travel(pos+1, temp_sum+toppingCosts[pos])\n",
    "            travel(pos+1, temp_sum+toppingCosts[pos]*2)\n",
    "        \n",
    "        travel(0, 0)\n",
    "\n",
    "        return self.ans\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        self.ans = baseCosts[0]\n",
    "        for baseCost in baseCosts:\n",
    "            self.dfs(toppingCosts, baseCost, target, 0)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, toppingCosts, sumCost, target, index):\n",
    "        if self.ans == target or (sumCost - target) > abs(self.ans - target):\n",
    "            return\n",
    "        if abs(sumCost - target) == abs(self.ans - target):\n",
    "            self.ans = min(sumCost, self.ans)\n",
    "        elif (abs(sumCost - target) < abs(self.ans - target)):\n",
    "            self.ans = sumCost\n",
    "        if (index >= len(toppingCosts)):\n",
    "            return\n",
    "        self.dfs(toppingCosts, sumCost, target, index + 1)\n",
    "        self.dfs(toppingCosts, sumCost + toppingCosts[index], target, index + 1)\n",
    "        self.dfs(toppingCosts, sumCost + 2 * toppingCosts[index], target, index + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        def dfs(p, cur_cost):\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts): return\n",
    "            dfs(p+1, cur_cost + toppingCosts[p]*2)\n",
    "            dfs(p+1, cur_cost + toppingCosts[p])\n",
    "            dfs(p+1, cur_cost)\n",
    "        ans = min(baseCosts)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans    \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "\n",
    "        def dfs(cur_cost: int, j: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                # 当前开销大于目前已知的最优值，就不需要往下递归了\n",
    "                return\n",
    "            \n",
    "            if abs(ans - target) > abs(cur_cost - target):\n",
    "                ans = cur_cost\n",
    "            elif abs(ans - target) == abs(cur_cost - target):\n",
    "                ans = min(ans, cur_cost)\n",
    "\n",
    "            if j == len(toppingCosts):\n",
    "                return\n",
    "            \n",
    "            dfs(cur_cost, j + 1)\n",
    "            dfs(cur_cost + toppingCosts[j], j + 1)\n",
    "            dfs(cur_cost + toppingCosts[j] * 2, j + 1)\n",
    "\n",
    "        for c in baseCosts:\n",
    "            dfs(c, 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ret = 1 << 30\n",
    "        n = len(toppingCosts)\n",
    "        def dfs(idx, val):\n",
    "            if idx == n:\n",
    "                nonlocal ret\n",
    "                a = abs(val - target)\n",
    "                b = abs(ret - target)\n",
    "                if a < b or (a == b and val < ret):\n",
    "                    ret = val    \n",
    "                return\n",
    "            for i in range(3):\n",
    "                dfs(idx + 1, val + i * toppingCosts[idx])\n",
    "        for x in baseCosts:\n",
    "            dfs(0, x)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        res, min_dif, n = float('inf'), float('inf'), len(toppingCosts)\n",
    "\n",
    "        def dfs(i, cur_tot):\n",
    "            nonlocal res, min_dif, n\n",
    "            if i == n:\n",
    "                dif = abs(cur_tot - target)\n",
    "                if dif < min_dif or dif == min_dif and cur_tot < res:\n",
    "                    res = cur_tot\n",
    "                    min_dif = dif\n",
    "                return\n",
    "            dfs(i + 1, cur_tot)\n",
    "            dfs(i + 1, cur_tot + toppingCosts[i])\n",
    "            dfs(i + 1, cur_tot + toppingCosts[i] * 2)\n",
    "                \n",
    "        for b in baseCosts:\n",
    "            dfs(0, b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        for k in baseCosts:\n",
    "            if k == target:\n",
    "                return target\n",
    "\n",
    "        top = toppingCosts + toppingCosts\n",
    "\n",
    "        # baseCosts.sort()\n",
    "        # if baseCosts[0] > target:\n",
    "        #     return baseCosts[0]\n",
    "\n",
    "        base_value = 20000 #target + baseCosts[-1]\n",
    "        ds = [0] * base_value\n",
    "\n",
    "        # top.sort()\n",
    "\n",
    "        m = len(toppingCosts) * 2\n",
    "        for i in range(1, m+1):\n",
    "            ls = itertools.combinations(top, i)\n",
    "            for l in ls:\n",
    "                s = sum(l)\n",
    "                if s < base_value:\n",
    "                    ds[s] = 1\n",
    "\n",
    "        better_value = baseCosts[0]\n",
    "\n",
    "        def get_better(a, b, tgt):\n",
    "            if abs(tgt - a) > abs(tgt - b):\n",
    "                return b\n",
    "            elif abs(tgt - a) < abs(tgt - b):\n",
    "                return a\n",
    "            else:\n",
    "                return min(a, b)\n",
    "\n",
    "        for b in baseCosts:\n",
    "            better_value = get_better(better_value, b, target)\n",
    "            diff = target - b\n",
    "            if diff < 0:\n",
    "                continue\n",
    "            if ds[diff] == 1:\n",
    "                return target\n",
    "            N = base_value - diff if base_value - diff > diff else diff\n",
    "            for m in range(1, N):\n",
    "                if diff - m > 0 and ds[diff - m] == 1:\n",
    "                    better_value = get_better(target - m, better_value, target)\n",
    "                    break\n",
    "                if diff + m < base_value and ds[diff + m] == 1:\n",
    "                    better_value = get_better(target + m, better_value, target)\n",
    "                    break\n",
    "\n",
    "        return better_value\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        result, n = float('inf'), len(toppingCosts)\n",
    "\n",
    "        def dfs(start: int, total: int) -> NoReturn:\n",
    "            nonlocal result\n",
    "            if (cur := abs(result - target) - abs(total - target)) > 0 or not cur and total < result:\n",
    "                result = total\n",
    "            if total >= target or start == n:\n",
    "                return \n",
    "            for i in range(3):\n",
    "                dfs(start + 1, total + toppingCosts[start] * i)\n",
    "        for base in baseCosts:\n",
    "            dfs(0, base)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, \n",
    "                    baseCosts: List[int], \n",
    "                    toppingCosts: List[int], \n",
    "                    target: int) -> int:\n",
    "\n",
    "        toppingCosts.sort()\n",
    "        m, n = len(toppingCosts), len(baseCosts)\n",
    "        ans, path = sys.maxsize, 0\n",
    "        hasans, hasbest = False, True\n",
    "        def dfs(k):\n",
    "            nonlocal ans, path, baseCosts\n",
    "            nonlocal hasans, hasbest\n",
    "            if hasans:\n",
    "                hasbest = False\n",
    "            if k >= m:\n",
    "                for b in baseCosts:\n",
    "                    if abs(target - ans) > abs(target - path - b):\n",
    "                        ans = path + b\n",
    "                        hasans, hasbest = True, True\n",
    "                    if abs(target - ans) == abs(target - path - b):\n",
    "                        if path + b < ans:\n",
    "                            ans = path + b\n",
    "                            hasans, hasbest = True, True\n",
    "                return hasbest\n",
    "            for i in range(k, m):\n",
    "                for j in range(0, 3):\n",
    "                    path += j * toppingCosts[i]\n",
    "                    dfs(i + 1)\n",
    "                    path -= j * toppingCosts[i]\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        for k in baseCosts:\n",
    "            if k == target:\n",
    "                return target\n",
    "\n",
    "        top = toppingCosts + toppingCosts\n",
    "\n",
    "        baseCosts.sort()\n",
    "        if baseCosts[0] > target:\n",
    "            return baseCosts[0]\n",
    "\n",
    "        base_value = 20000 #target + baseCosts[-1]\n",
    "        ds = [0] * base_value\n",
    "\n",
    "        # top.sort()\n",
    "\n",
    "        m = len(toppingCosts) * 2\n",
    "        for i in range(1, m+1):\n",
    "            ls = itertools.combinations(top, i)\n",
    "            for l in ls:\n",
    "                s = sum(l)\n",
    "                if s < base_value:\n",
    "                    ds[s] = 1\n",
    "\n",
    "        better_value = baseCosts[0]\n",
    "\n",
    "        def get_better(a, b, tgt):\n",
    "            if abs(tgt - a) > abs(tgt - b):\n",
    "                return b\n",
    "            elif abs(tgt - a) < abs(tgt - b):\n",
    "                return a\n",
    "            else:\n",
    "                return min(a, b)\n",
    "\n",
    "        for b in baseCosts:\n",
    "            better_value = get_better(better_value, b, target)\n",
    "            diff = target - b\n",
    "            if diff < 0:\n",
    "                break\n",
    "            if ds[diff] == 1:\n",
    "                return target\n",
    "            N = base_value - diff if base_value - diff > diff else diff\n",
    "            for m in range(1, N):\n",
    "                if diff - m > 0 and ds[diff - m] == 1:\n",
    "                    better_value = get_better(target - m, better_value, target)\n",
    "                    break\n",
    "                if diff + m < base_value and ds[diff + m] == 1:\n",
    "                    better_value = get_better(target + m, better_value, target)\n",
    "                    break\n",
    "\n",
    "        return better_value\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        res = min(baseCosts)\n",
    "        def dfs(p,cur_cost):\n",
    "            nonlocal res\n",
    "            if cur_cost - target > abs(res - target):\n",
    "                return \n",
    "            if abs(cur_cost - target) <= abs(res - target):\n",
    "                if abs(cur_cost - target) < abs(res - target):\n",
    "                    res = cur_cost\n",
    "                else:\n",
    "                    res = min(res,cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return \n",
    "\n",
    "            dfs(p+1,cur_cost+0)\n",
    "            dfs(p+1,cur_cost+toppingCosts[p])\n",
    "            dfs(p+1,cur_cost+toppingCosts[p]*2)\n",
    "\n",
    "\n",
    "\n",
    "        for c in baseCosts:\n",
    "            dfs(0,c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        max_target = 2*target\n",
    "        dp = [False]*(2*target+1)\n",
    "        min_base = inf\n",
    "        for base in baseCosts:\n",
    "            if min_base > base:\n",
    "                min_base = base\n",
    "            if base >max_target:\n",
    "                continue\n",
    "            dp[base] = True\n",
    "        if min_base>target:\n",
    "            return min_base\n",
    "        topping = toppingCosts+toppingCosts\n",
    "        for t in topping:\n",
    "            if max_target-t<0:\n",
    "                continue\n",
    "            for i in range(max_target, t-1, -1 ):\n",
    "                dp[i] = dp[i] or dp[i-t]\n",
    "        for i in range(target+1):\n",
    "            if  dp[target-i]:\n",
    "                return target-i\n",
    "            if dp[target+i]:\n",
    "                return target+i\n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        对于每一种配料，只有三种搜索情况\n",
    "        1.不选\n",
    "        2.选1次\n",
    "        3.选2次\n",
    "    '''\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = inf\n",
    "        smaller = inf\n",
    "        def dfs(i: int, v: int):\n",
    "            nonlocal ans, smaller\n",
    "            if v - target > abs(ans - target): # 剪枝，当前已经大于最小的与target的差值，后面的v只会越来越大\n",
    "                return\n",
    "            if i >= len(toppingCosts):\n",
    "                diff = abs(v - target)\n",
    "                if diff < smaller:\n",
    "                    ans = v\n",
    "                    smaller = diff\n",
    "                elif diff == smaller:\n",
    "                    ans = min(ans, v)\n",
    "                return\n",
    "            dfs(i + 1, v)\n",
    "            dfs(i + 1, v + toppingCosts[i])\n",
    "            dfs(i + 1, v + 2 * toppingCosts[i])\n",
    "        for b in baseCosts:\n",
    "            dfs(0, b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        sign, res = 1, float('inf')\n",
    "        def dfs(i, rest, s):\n",
    "            nonlocal sign \n",
    "            nonlocal res \n",
    "            if i == m or s == 1:\n",
    "                if rest < res:\n",
    "                    res = rest \n",
    "                    sign = s \n",
    "                elif rest == res and s == -1:\n",
    "                    sign = -1 \n",
    "                return \n",
    "            for k in range(min(2, rest//toppingCosts[i] + 1) + 1):\n",
    "                r = rest - k * toppingCosts[i] \n",
    "                dfs(i+1, abs(r), 1 if r < 0 else -1)\n",
    "        for i in range(n):\n",
    "            if target >= baseCosts[i]:\n",
    "                dfs(0, target-baseCosts[i], -1)\n",
    "            else:\n",
    "                dfs(0, -target+baseCosts[i], 1)\n",
    "        return target + res * sign \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n = len(baseCosts)\n",
    "        toppingCosts = [toppingCosts[i//2] for i in range(len(toppingCosts)*2)]\n",
    "        m = len(toppingCosts)\n",
    "        best_cost = float('inf')\n",
    "        \n",
    "        dp = [False]*(target+1)\n",
    "        for i in range(n):\n",
    "            if baseCosts[i]<=target:\n",
    "                dp[baseCosts[i]] = True\n",
    "            else:\n",
    "                best_cost = min(best_cost, baseCosts[i])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(target,-1,-1):\n",
    "                x = toppingCosts[i]\n",
    "                if dp[j] and j+x>target:\n",
    "                    best_cost = min(best_cost, j+x)\n",
    "                if j>=x:\n",
    "                    dp[j] = dp[j] or dp[j-x]\n",
    "                pass\n",
    "        \n",
    "        cur_diff = best_cost - target\n",
    "        d = 0\n",
    "        while d<=cur_diff and d<=target:\n",
    "            if dp[target-d]:\n",
    "                return target-d\n",
    "            d+=1\n",
    "        return best_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        arr = [inf, inf]\n",
    "        def calc(v):\n",
    "            t_abs = abs(v - target)\n",
    "            if arr[0] > t_abs:\n",
    "                arr[0] = t_abs\n",
    "                arr[1] = v\n",
    "            elif arr[0] == t_abs and arr[1] > v:\n",
    "                arr[1] = v\n",
    "        def dfs(i, v):\n",
    "            if i == m:\n",
    "                calc(v)\n",
    "                return\n",
    "            for j in range(3):\n",
    "                dfs(i+1, v + toppingCosts[i] * j)\n",
    "        for v in baseCosts:\n",
    "            if v < target:\n",
    "                dfs(0, v)\n",
    "            else:\n",
    "                calc(v)\n",
    "        return arr[1]          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, \n",
    "                    baseCosts: List[int], \n",
    "                    toppingCosts: List[int], \n",
    "                    target: int) -> int:\n",
    "\n",
    "        baseCosts.sort()\n",
    "        toppingCosts.sort()\n",
    "\n",
    "        n = len(toppingCosts)\n",
    "        ans = sys.maxsize\n",
    "        path = []\n",
    "\n",
    "        def dfs(b, v, k):\n",
    "            nonlocal ans\n",
    "            cur = b + v\n",
    "            if abs(cur - target) < abs(ans - target):\n",
    "                ans = cur\n",
    "            elif abs (cur - target) == abs(ans - target):\n",
    "                if cur < ans:\n",
    "                    ans = cur\n",
    "            else:\n",
    "                if cur > target:\n",
    "                    return\n",
    "            if k == n:\n",
    "                return\n",
    "            \n",
    "            dfs(b, v, k + 1)\n",
    "            dfs(b, v + toppingCosts[k], k + 1)\n",
    "            dfs(b, v + 2 * toppingCosts[k], k + 1)\n",
    "        \n",
    "        for b in baseCosts:\n",
    "            if b == target:\n",
    "                return b\n",
    "            dfs(b, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        closest = float('inf')  # 初始化为无穷大，用于记录与目标价格最接近的组合\n",
    "        \n",
    "        # 使用回溯算法找出所有可能的配料组合\n",
    "        def backtrack(start, cur_cost):\n",
    "            nonlocal closest\n",
    "            \n",
    "            # 更新最接近的成本\n",
    "            if abs(target - cur_cost) < abs(target - closest) or \\\n",
    "               (abs(target - cur_cost) == abs(target - closest) and cur_cost < closest):\n",
    "                closest = cur_cost\n",
    "            \n",
    "            if cur_cost >= target:\n",
    "                return\n",
    "            \n",
    "            for i in range(start, len(toppingCosts)):\n",
    "                # 尝试添加0份、1份或2份配料\n",
    "                for j in range(3):\n",
    "                    backtrack(i + 1, cur_cost + toppingCosts[i] * j)\n",
    "        \n",
    "        # 对每一种冰激凌基料，使用回溯算法找出所有可能的配料组合\n",
    "        for base in baseCosts:\n",
    "            backtrack(0, base)\n",
    "        \n",
    "        return closest\n",
    "\n",
    "# 测试用例\n",
    "baseCosts = [10]\n",
    "toppingCosts = [1]\n",
    "target = 1\n",
    "solution = Solution()\n",
    "print(solution.closestCost(baseCosts, toppingCosts, target))  # 输出应为10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        has, n, mx = set(), len(toppingCosts), 20000\n",
    "        for i in baseCosts:\n",
    "            if i == target: return target\n",
    "            elif i < target: has.add(i)\n",
    "            elif i < mx: mx = i\n",
    "        if not has: return mx\n",
    "        for v in toppingCosts:\n",
    "            for i in list(has):\n",
    "                for nv in [i+v, i+2*v]:\n",
    "                    if nv <= target: has.add(nv)\n",
    "                    elif nv < mx: mx = nv\n",
    "            if target in has: return target\n",
    "        mn = max(has)\n",
    "        return mn if mx + mn >= 2 * target else mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = inf\n",
    "        def dfs(p=0, i=0):\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) > abs(p - target):\n",
    "                ans = p\n",
    "            elif abs(ans - target) == abs(p - target):\n",
    "                ans = min(p, ans)\n",
    "            if i == len(toppingCosts):\n",
    "                return \n",
    "            dfs(p, i + 1)\n",
    "            dfs(p+toppingCosts[i], i + 1)\n",
    "            dfs(p+toppingCosts[i]*2, i + 1)\n",
    "            \n",
    "        for x in baseCosts:\n",
    "            dfs(x, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        has, n, mx = set(), len(toppingCosts), 20000\n",
    "        for i in baseCosts:\n",
    "            if i == target: return target\n",
    "            elif i < target: has.add(i)\n",
    "            elif i < mx: mx = i\n",
    "        if not has: return mx\n",
    "        for v in toppingCosts:\n",
    "            for i in list(has):\n",
    "                for nv in [i+v, i+2*v]:\n",
    "                    if nv <= target: has.add(nv)\n",
    "                    elif nv < mx: mx = nv\n",
    "            if target in has: return target\n",
    "        mn = max(has)\n",
    "        return mn if mx + mn >= 2 * target else mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        def check(a,b):\n",
    "            if abs(target-a)==abs(target-b):\n",
    "                return [b,a][a<b]\n",
    "            elif abs(target-a)<abs(target-b):\n",
    "                return a\n",
    "            return b\n",
    "        res=inf\n",
    "        n=len(toppingCosts)\n",
    "        for tmp in range(3**n):\n",
    "            ans=0\n",
    "            for i in range(n):\n",
    "                if tmp%3==2:\n",
    "                    ans+=2*toppingCosts[i]\n",
    "                elif tmp%3==1:\n",
    "                    ans+=toppingCosts[i]\n",
    "                tmp//=3\n",
    "            for b in baseCosts:\n",
    "                res=check(res,b+ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        mn = float('inf')\n",
    "        ans = float('inf')\n",
    "        def dfs(i, tot):\n",
    "            nonlocal mn, ans \n",
    "            if abs(tot - target) < mn:\n",
    "                mn = abs(tot - target)\n",
    "                ans = tot\n",
    "            elif abs(tot - target) == mn and tot < ans:\n",
    "                ans = tot   \n",
    "            if i < m:\n",
    "                for k in range(3):\n",
    "                    dfs(i+1, tot + k * toppingCosts[i])\n",
    "        for x in baseCosts:\n",
    "            dfs(0, x) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        x = min(baseCosts)\n",
    "        if x >= target:\n",
    "            return x\n",
    "        # can[i]制作开销i为是否存在合法方案\n",
    "        can = [False]*(target+1)\n",
    "        ans = 2*target-x\n",
    "        for b in baseCosts:\n",
    "            if b <= target:\n",
    "                can[b] = True\n",
    "            else:\n",
    "                ans = min(ans,b)\n",
    "        for t in toppingCosts:\n",
    "            for c in range(2):\n",
    "                for i in range(target,0,-1):\n",
    "                    if can[i] and i+t> target:\n",
    "                        ans = min(ans,i+t)\n",
    "                    if i-t > 0 and not can[i]:\n",
    "                        can[i] = can[i-t]\n",
    "        for i in range(ans-target+1):\n",
    "            if can[target-i]:\n",
    "                return target-i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        max_target = 2*target\n",
    "        dp = [False]*(2*target+1)\n",
    "        # dp[0] = True\n",
    "        min_base = inf\n",
    "        for base in baseCosts:\n",
    "            if min_base > base:\n",
    "                min_base = base\n",
    "            if base >max_target:\n",
    "                continue\n",
    "   \n",
    "            dp[base] = True\n",
    "        if min_base>target:\n",
    "            return min_base\n",
    "        topping = toppingCosts+toppingCosts\n",
    "        # for \n",
    "        for t in topping:\n",
    "            if max_target-t<0:\n",
    "                continue\n",
    "            for i in range(max_target, t-1, -1 ):\n",
    "\n",
    "                dp[i] = dp[i] or dp[i-t]\n",
    "        # print(dp)\n",
    "        for i in range(target+1):\n",
    "            if  dp[target-i]:\n",
    "                return target-i\n",
    "            if dp[target+i]:\n",
    "                return target+i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        arr = [inf, inf]\n",
    "        def dfs(i, v):\n",
    "            if i == m:\n",
    "                if arr[0] > abs(v - target):\n",
    "                    arr[0] = abs(v - target)\n",
    "                    arr[1] = v\n",
    "                elif arr[0] == abs(v - target) and arr[1] > v:\n",
    "                    arr[1] = v\n",
    "                return\n",
    "            for j in range(3):\n",
    "                dfs(i+1, v + toppingCosts[i] * j)\n",
    "        for b in baseCosts:\n",
    "            dfs(0, b)\n",
    "        return arr[1]          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        res = min(baseCosts)\n",
    "        n = len(baseCosts)\n",
    "        def dfs(p,current_cost):\n",
    "            nonlocal res\n",
    "            if current_cost-target>abs(res-target):\n",
    "                return\n",
    "            if abs(current_cost-target)<=abs(res-target):\n",
    "                if abs(current_cost-target)<abs(res-target):\n",
    "                    res = current_cost\n",
    "                else:\n",
    "                    res = min(res,current_cost)\n",
    "            if p==len(toppingCosts):\n",
    "                return\n",
    "            dfs(p+1,current_cost)\n",
    "            dfs(p+1,current_cost+toppingCosts[p])\n",
    "            dfs(p+1,current_cost+toppingCosts[p]*2)\n",
    "        for c in baseCosts:\n",
    "            dfs(0,c)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "             \n",
    "        \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        mn = float('inf')\n",
    "        ans = float('inf')\n",
    "        def dfs(i, tot):\n",
    "            nonlocal mn, ans \n",
    "            if i == m:\n",
    "                if abs(tot - target) < mn:\n",
    "                    mn = abs(tot - target)\n",
    "                    ans = tot\n",
    "                elif abs(tot - target) == mn and tot < ans:\n",
    "                    ans = tot   \n",
    "            if i < m:\n",
    "                for k in range(3):\n",
    "                    dfs(i+1, tot + k * toppingCosts[i])\n",
    "        for x in baseCosts:\n",
    "            dfs(0, x) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        n = len(toppingCosts)\n",
    "        def dfs(i,cost):\n",
    "            nonlocal ans\n",
    "            # 表示从下标i的配料开始选择，当前的成本为cost\n",
    "            if abs(ans-target) < cost-target:\n",
    "                return \n",
    "            if abs(ans-target) >= abs(cost-target):\n",
    "                if abs(ans-target) > abs(cost-target):\n",
    "                    ans = cost\n",
    "                else:\n",
    "                    ans = min(ans,cost)\n",
    "            if i == n:\n",
    "                return \n",
    "            dfs(i+1,cost)\n",
    "            dfs(i+1,cost+toppingCosts[i])\n",
    "            dfs(i+1,cost+toppingCosts[i]*2)\n",
    "        for b in baseCosts:\n",
    "            dfs(0,b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        toppingCosts.sort()\n",
    "        baseCosts.sort()\n",
    "        m=len(baseCosts)\n",
    "        n=len(toppingCosts)\n",
    "        vis=[0]*n\n",
    "        mi=float(\"inf\")\n",
    "        ans=[]\n",
    "        def dfs(i,j,t):\n",
    "            nonlocal ans\n",
    "            nonlocal mi\n",
    "            if i==1 and j==n:\n",
    "                if t==target:\n",
    "                    ans=[t]\n",
    "                    mi=0\n",
    "                elif abs(t-target)<mi:\n",
    "                    mi=abs(t-target)\n",
    "                    ans=[t]\n",
    "                elif abs(t-target)==mi:\n",
    "                    ans.append(t)\n",
    "                return \n",
    "            if t-target>mi:\n",
    "                return \n",
    "            if i==0:\n",
    "                for x in range(m):\n",
    "                    dfs(i+1,j,t+baseCosts[x])\n",
    "            if j<n:\n",
    "                dfs(i,j+1,t+toppingCosts[j])\n",
    "                dfs(i,j+1,t+toppingCosts[j]*2)\n",
    "                dfs(i,j+1,t)\n",
    "\n",
    "            return \n",
    "        dfs(0,0,0)\n",
    "       # print(ans)\n",
    "        return sorted(ans)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "\n",
    "        def dfs(i, t):\n",
    "\n",
    "            if i >= len(toppingCosts):\n",
    "\n",
    "                arr.append(t)\n",
    "\n",
    "                return\n",
    "\n",
    "            dfs(i + 1, t)\n",
    "\n",
    "            dfs(i + 1, t + toppingCosts[i])\n",
    "\n",
    "\n",
    "\n",
    "        arr = []\n",
    "\n",
    "        dfs(0, 0)\n",
    "\n",
    "        arr.sort()\n",
    "\n",
    "        d = ans = inf\n",
    "\n",
    "\n",
    "\n",
    "        # 选择一种冰激淋基料\n",
    "\n",
    "        for x in baseCosts:\n",
    "\n",
    "            # 枚举子集和\n",
    "\n",
    "            for y in arr:\n",
    "\n",
    "                # 二分查找\n",
    "\n",
    "                i = bisect_left(arr, target - x - y)\n",
    "\n",
    "                for j in (i, i - 1):\n",
    "\n",
    "                    if 0 <= j < len(arr):\n",
    "\n",
    "                        t = abs(x + y + arr[j] - target)\n",
    "\n",
    "                        if d > t or (d == t and ans > x + y + arr[j]):\n",
    "\n",
    "                            d = t\n",
    "\n",
    "                            ans = x + y + arr[j]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        dp = [False]*(target+1)\n",
    "        ret = float('inf')\n",
    "        for b in baseCosts:\n",
    "            if b <= target: dp[b] = True\n",
    "            else: ret = min(ret, b)\n",
    "\n",
    "        for t in toppingCosts:\n",
    "            for d in range(target+1)[::-1]:\n",
    "                if dp[d]:\n",
    "                    if d+t <= target: dp[d+t] = True\n",
    "                    else: ret = min(ret, d+t)\n",
    "                    if d+2*t <= target: dp[d+2*t] = True\n",
    "                    else: ret = min(ret, d+2*t)\n",
    "        for idx, d in enumerate(dp):\n",
    "            if d and abs(idx-target) < abs(ret-target):\n",
    "                ret = idx\n",
    "            elif d and abs(idx-target) == abs(ret-target):\n",
    "                ret = min(idx, ret)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        diff = 50000\n",
    "        for i in baseCosts:\n",
    "            cont = set([i])\n",
    "            for j in toppingCosts:            \n",
    "                cont2 = set()\n",
    "                for k in cont:\n",
    "                    for i in range(3):\n",
    "                        curr = k + i * j\n",
    "                        d = curr - target\n",
    "                        if curr <= target + abs(diff): \n",
    "                            if abs(d) < abs(diff):\n",
    "                                diff = d\n",
    "                            elif abs(d) == abs(diff):\n",
    "                                diff = min(diff, d)\n",
    "                            cont2.add(curr)\n",
    "                cont = cont | cont2\n",
    "        return target + diff\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cmp_key(x):\n",
    "    return [abs(x), x]\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        dp = [-each for each in range(target + 1)]\n",
    "        for i in range(len(toppingCosts)):\n",
    "            for j in range(len(dp) - 1, -1, -1):\n",
    "                dp[j] = min(\n",
    "                    dp[j],\n",
    "                    dp[j-toppingCosts[i]] if j-toppingCosts[i] >= 0 else -(j-toppingCosts[i]),\n",
    "                    dp[j-2*toppingCosts[i]] if j-2*toppingCosts[i] >= 0 else -(j-2*toppingCosts[i]),\n",
    "                    key=cmp_key\n",
    "                )\n",
    "        \n",
    "        eachBaseMinDelta = (\n",
    "            dp[target-x] if target-x >= 0 else -(target-x)\n",
    "            for x in baseCosts\n",
    "        )\n",
    "        \n",
    "        minDelta = min(eachBaseMinDelta,\n",
    "                    key = cmp_key\n",
    "        )\n",
    "        return target+minDelta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        x = min(baseCosts)\n",
    "        if x > target:\n",
    "            return x\n",
    "        can = [False] * (target + 1)\n",
    "        ans = 2 * target - x # 取一个不可能的值\n",
    "        for c in baseCosts:\n",
    "            if c <= target:\n",
    "                can[c] = True\n",
    "            else:\n",
    "                ans = min(ans, c)\n",
    "        # 0-1背包，先物品后背包，背包逆序\n",
    "        for c in toppingCosts:\n",
    "            for count in range(2):\n",
    "                for i in range(target, 0, -1):\n",
    "                    # 大于则直接更新ans\n",
    "                    if can[i] and i + c > target:\n",
    "                        ans = min(ans, i + c)\n",
    "                    # 小于则先加上\n",
    "                    if i - c > 0 and not can[i]:\n",
    "                        can[i] = can[i - c]\n",
    "        for i in range(ans - target + 1):\n",
    "            if can[target - i]:\n",
    "                return target - i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, \n",
    "                    baseCosts: List[int], \n",
    "                    toppingCosts: List[int], \n",
    "                    target: int) -> int:\n",
    "\n",
    "        tab, ans, res = set(), maxsize, maxsize\n",
    "        for b in baseCosts:\n",
    "            if b == target:\n",
    "                return b\n",
    "            elif b < target:\n",
    "                tab.add(b)\n",
    "            else:\n",
    "                if ans > b:\n",
    "                    ans = b\n",
    "        if len(tab) == 0:\n",
    "            return ans\n",
    "\n",
    "        for t in toppingCosts:\n",
    "            for e in list(tab):\n",
    "                for v in [e + t, e + 2*t]:\n",
    "                    if v == target:\n",
    "                        return target\n",
    "                    elif v < target:\n",
    "                        tab.add(v)\n",
    "                    else:\n",
    "                        if ans > v:\n",
    "                            ans = v\n",
    "        res = max(tab)\n",
    "        if abs(res - target) <= abs(ans - target):\n",
    "            return res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        has, n, mx = set(), len(toppingCosts), 20000\n",
    "        for i in baseCosts:\n",
    "            if i == target: return target\n",
    "            elif i < target: has.add(i)\n",
    "            elif i < mx: mx = i\n",
    "        if not has: return mx\n",
    "        for v in toppingCosts:\n",
    "            for i in list(has):\n",
    "                for nv in [i+v, i+2*v]:\n",
    "                    if nv <= target: has.add(nv)\n",
    "                    elif nv < mx: mx = nv\n",
    "            if target in has: return target\n",
    "        mn = max(has)\n",
    "        return mn if mx + mn >= 2 * target else mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 回溯\n",
    "    # O(n × 3^m) O(m)\n",
    "    def closestCost1(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        ans = min(baseCosts)\n",
    "        def dfs(p: int, cur_cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if abs(ans - target) < cur_cost - target:\n",
    "                return\n",
    "\n",
    "            if abs(ans - target) >= abs(cur_cost - target):\n",
    "                if abs(ans - target) > abs(cur_cost - target):\n",
    "                    ans = cur_cost\n",
    "                else:\n",
    "                    ans = min(ans, cur_cost)\n",
    "\n",
    "            if p == len(toppingCosts):\n",
    "                return\n",
    "\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p] * 2)\n",
    "            dfs(p + 1, cur_cost + toppingCosts[p])\n",
    "            dfs(p + 1, cur_cost)\n",
    "\n",
    "        for c in baseCosts:\n",
    "            dfs(0, c)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    # dp\n",
    "    # 01 背包\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        x = min(baseCosts)\n",
    "        if x > target:\n",
    "            return x\n",
    "\n",
    "        can = [False] * (target + 1)\n",
    "        ans = 2 * target - x\n",
    "        for c in baseCosts:\n",
    "            if c <= target:\n",
    "                can[c] = True\n",
    "            else:\n",
    "                ans = min(ans, c)\n",
    "\n",
    "        for c in toppingCosts:\n",
    "            for count in range(2):\n",
    "                for i in range(target, 0, -1):\n",
    "                    if can[i] and i + c > target:\n",
    "                        ans = min(ans, i + c)\n",
    "\n",
    "                    if i - c > 0 and not can[i]:\n",
    "                        can[i] = can[i - c]\n",
    "\n",
    "        for i in range(ans - target + 1):\n",
    "            if can[target - i]:\n",
    "                return target - i\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        def dfs(i, t):\n",
    "            if i >= len(toppingCosts):\n",
    "                arr.append(t)\n",
    "                return\n",
    "            dfs(i + 1, t)\n",
    "            dfs(i + 1, t + toppingCosts[i])\n",
    "\n",
    "        arr = []\n",
    "        dfs(0, 0)\n",
    "        arr.sort()\n",
    "        d = ans = inf\n",
    "\n",
    "        # 选择一种冰激淋基料\n",
    "        for x in baseCosts:\n",
    "            # 枚举子集和\n",
    "            for y in arr:\n",
    "                # 二分查找\n",
    "                i = bisect_left(arr, target - x - y)\n",
    "                for j in (i, i - 1):\n",
    "                    if 0 <= j < len(arr):\n",
    "                        t = abs(x + y + arr[j] - target)\n",
    "                        if d > t or (d == t and ans > x + y + arr[j]):\n",
    "                            d = t\n",
    "                            ans = x + y + arr[j]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        dp = [False]*(target+1)\n",
    "        ret = float('inf')\n",
    "        for b in baseCosts:\n",
    "            if b <= target: dp[b] = True\n",
    "            else: ret = min(ret, b)\n",
    "\n",
    "        for t in toppingCosts:\n",
    "            tmp = dp[:]\n",
    "            for d, v in enumerate(dp):\n",
    "                if v:\n",
    "                    if d+t <= target: tmp[d+t] = True\n",
    "                    else: ret = min(ret, d+t)\n",
    "                    if d+2*t <= target: tmp[d+2*t] = True\n",
    "                    else: ret = min(ret, d+2*t)\n",
    "            dp = tmp[:]\n",
    "        for idx, d in enumerate(dp):\n",
    "            if d and abs(idx-target) < abs(ret-target):\n",
    "                ret = idx\n",
    "            elif d and abs(idx-target) == abs(ret-target):\n",
    "                ret = min(idx, ret)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        def dfs(i, t):\n",
    "            if i >= len(toppingCosts):\n",
    "                arr.append(t)\n",
    "                return\n",
    "            dfs(i + 1, t)\n",
    "            dfs(i + 1, t + toppingCosts[i])\n",
    "\n",
    "        arr = []\n",
    "        dfs(0, 0)\n",
    "        arr.sort()\n",
    "        d = ans = inf\n",
    "\n",
    "        # 选择一种冰激淋基料\n",
    "        for x in baseCosts:\n",
    "            # 枚举子集和\n",
    "            for y in arr:\n",
    "                # 二分查找\n",
    "                i = bisect_left(arr, target - x - y)\n",
    "                for j in (i, i - 1):\n",
    "                    if 0 <= j < len(arr):\n",
    "                        t = abs(x + y + arr[j] - target)\n",
    "                        if d > t or (d == t and ans > x + y + arr[j]):\n",
    "                            d = t\n",
    "                            ans = x + y + arr[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "\n",
    "        ## 每种配料最多两份 一种或多种配料\n",
    "        ## 只能一种基料\n",
    "        ## \n",
    "\n",
    "        ## 返回最接近target的甜点成本\n",
    "\n",
    "        ## n m\n",
    "        ## \n",
    "        ## n*m\n",
    "        ## 陷入了什么误区\n",
    "        ## dfs遍历情况 + cache缓存机制 其实就是一种动态规划！！\n",
    "        ## 记忆化搜索\n",
    "\n",
    "        \n",
    "        \n",
    "        ## 这道题目为判断组合是否存在的问题 每个配料有两种\n",
    "\n",
    "        n = len(toppingCosts)\n",
    "        dp = [[False]*(12000) for _ in range(n+1)]\n",
    "\n",
    "        for base in baseCosts:\n",
    "            dp[0][base] = True\n",
    "\n",
    "        toppingCosts = [0] + toppingCosts\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,12000):\n",
    "                b = False\n",
    "                k = 0\n",
    "                while k <= 2 and j - toppingCosts[i]*k >=0:\n",
    "                    b |= dp[i-1][j-toppingCosts[i]*k]\n",
    "                    k += 1\n",
    "                dp[i][j] |= b\n",
    "\n",
    "\n",
    "        \n",
    "        ans = 0\n",
    "        dis = inf\n",
    "        for i in range(12000):\n",
    "            if dp[n][i]:\n",
    "                cur = abs(target - i)\n",
    "                if cur < dis:\n",
    "                    ans = i\n",
    "                    dis = cur\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n, m = len(baseCosts), len(toppingCosts)\n",
    "        dp = [False]*(target+1)\n",
    "        ret = float('inf')\n",
    "        for b in baseCosts:\n",
    "            if b <= target: dp[b] = True\n",
    "            else: ret = min(ret, b)\n",
    "\n",
    "        for t in toppingCosts:\n",
    "            # tmp = dp[:]\n",
    "            for d, v in list(enumerate(dp))[::-1]:\n",
    "                if v:\n",
    "                    if d+t <= target: dp[d+t] = True\n",
    "                    else: ret = min(ret, d+t)\n",
    "                    if d+2*t <= target: dp[d+2*t] = True\n",
    "                    else: ret = min(ret, d+2*t)\n",
    "            # dp = tmp[:]\n",
    "        for idx, d in enumerate(dp):\n",
    "            if d and abs(idx-target) < abs(ret-target):\n",
    "                ret = idx\n",
    "            elif d and abs(idx-target) == abs(ret-target):\n",
    "                ret = min(idx, ret)\n",
    "        return ret\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        n = len(baseCosts)\n",
    "        toppingCosts = [toppingCosts[i//2] for i in range(len(toppingCosts)*2)]\n",
    "        m = len(toppingCosts)\n",
    "        best_cost = float('inf')\n",
    "        \n",
    "        dp = [[False]*(target+1) for _ in range(m+1)]\n",
    "        # for i in range(m+1):\n",
    "        #     dp[i][0] = True\n",
    "        for i in range(n):\n",
    "            if baseCosts[i]<=target:\n",
    "                dp[0][baseCosts[i]] = True\n",
    "            else:\n",
    "                best_cost = min(best_cost, baseCosts[i])\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,target+1):\n",
    "                x = toppingCosts[i-1]\n",
    "                if dp[i-1][j] and j+x>target:\n",
    "                    best_cost = min(best_cost, j+x)\n",
    "                if j<x:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-x]\n",
    "                pass\n",
    "        \n",
    "        cur_diff = best_cost - target\n",
    "        d = 0\n",
    "        while d<=cur_diff and d<=target:\n",
    "            if dp[-1][target-d]:\n",
    "                return target-d\n",
    "            d+=1\n",
    "        return best_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        #copy\n",
    "        @cache\n",
    "        def dfs(cur,idx):\n",
    "            if idx == len(toppingCosts) or cur >= target:\n",
    "                return cur,abs(cur-target)\n",
    "            ans,diff = inf,inf\n",
    "            for i in range(3):\n",
    "                res=dfs(cur+ toppingCosts[idx]*i,idx+1)\n",
    "                if res[1]<diff:\n",
    "                    ans,diff = res\n",
    "                elif res[1]== diff:\n",
    "                    ans = min(ans,res[0])\n",
    "            return ans,diff\n",
    "        \n",
    "        r,d = inf,inf\n",
    "        for b in baseCosts:\n",
    "            c= dfs(b,0)\n",
    "            if c[1]<d:\n",
    "                r,d=c\n",
    "            elif c[1] == d:\n",
    "                r= min(r,c[0])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "        return min((abs(target-(s:=i+j)), s) for i in baseCosts for j in set(sum(j) for i in range(len(toppingCosts) << 1) for j in combinations(toppingCosts + toppingCosts, i+1)).union({0}))[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 10 ** 9\n",
    "\n",
    "    def closestCost(self, base_costs: List[int], topping_costs: List[int], target: int) -> int:\n",
    "        size = len(topping_costs)\n",
    "        topping_costs.sort()\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, now):\n",
    "            \"\"\"深度优先搜索:i=当前配料位置，now=当前总成本\"\"\"\n",
    "            if i == size or now > target:\n",
    "                if (abs(now - target) < abs(self.ans - target) or\n",
    "                        (abs(now - target) == abs(self.ans - target) and now < self.ans)):\n",
    "                    self.ans = now\n",
    "                return\n",
    "\n",
    "            for k in [0, 1, 2]:\n",
    "                dfs(i + 1, now + k * topping_costs[i])\n",
    "\n",
    "        for v in base_costs:\n",
    "            dfs(0, v)\n",
    "\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n",
    "       def dfs(i: int, j: int) -> None:\n",
    "          if i == m:\n",
    "             s.add(j)\n",
    "             return\n",
    "          for k in range(3):\n",
    "             dfs(i + 1, j + toppingCosts[i] * k)\n",
    "       s = set()\n",
    "       m = len(toppingCosts)\n",
    "       dfs(0, 0)\n",
    "       _list = list(s)\n",
    "       _list.sort()\n",
    "       diff = inf\n",
    "       res = inf\n",
    "       baseCosts.sort()\n",
    "       for base in baseCosts:\n",
    "          if base - target >= diff:\n",
    "             continue\n",
    "          for top in _list:\n",
    "             _sum = base + top\n",
    "             if abs(_sum - target) < diff:\n",
    "                diff = abs(_sum - target)\n",
    "                res = _sum\n",
    "             elif abs(_sum - target) == diff and _sum < res:\n",
    "                res = _sum\n",
    "             if diff == 0:\n",
    "                return target\n",
    "       return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
